9.5 Sorting Sequences

Function: cl-sort seq predicate &key :key

This function sorts seq into increasing order as determined by using predicate to compare pairs of elements. predicate should return true (non-nil) if and only if its first argument is less than (not equal to) its second argument. For example, < and string-lessp are suitable predicate functions for sorting numbers and strings, respectively; > would sort numbers into decreasing rather than increasing order.

This function differs from Emacs’s built-in sort in that it can operate on any type of sequence, not just lists. Also, it accepts a :key argument, which is used to preprocess data fed to the predicate function. For example,

(setq data (cl-sort data 'string-lessp :key 'downcase))

sorts data, a sequence of strings, into increasing alphabetical order without regard to case. A :key function of car would be useful for sorting association lists. It should only be a simple accessor though, since it’s used heavily in the current implementation.

The cl-sort function is destructive; it sorts lists by actually rearranging the CDR pointers in suitable fashion.

Function: cl-stable-sort seq predicate &key :key

This function sorts seq stably, meaning two elements which are equal in terms of predicate are guaranteed not to be rearranged out of their original order by the sort.

In practice, cl-sort and cl-stable-sort are equivalent in Emacs Lisp because the underlying sort function is stable by default. However, this package reserves the right to use non-stable methods for cl-sort in the future.

Function: cl-merge type seq1 seq2 predicate &key :key

This function merges two sequences seq1 and seq2 by interleaving their elements. The result sequence, of type type (in the sense of cl-concatenate), has length equal to the sum of the lengths of the two input sequences. The sequences may be modified destructively. Order of elements within seq1 and seq2 is preserved in the interleaving; elements of the two sequences are compared by predicate (in the sense of sort) and the lesser element goes first in the result. When elements are equal, those from seq1 precede those from seq2 in the result. Thus, if seq1 and seq2 are both sorted according to predicate, then the result will be a merged sequence which is (stably) sorted according to predicate.